#!/usr/bin/python

# make_kmap.py

import sys
import operator
import itertools

def kmap(file = sys.stdout, **questions):
    r'''Prints a K-map for the questions to stdout.

    The K-map looks like:

               q1
               |q2
               YY YN Y? NY NN N? ?Y ?N ??
           ---+--+--+--+--+--+--+--+--+--+
       q q YY |  |  |  |  |  |  |  |  |  |
       3 4 ---+--+--+--+--+--+--+--+--+--+
           YN |  |  |  |  |  |  |  |  |  |
           ---+--+--+--+--+--+--+--+--+--+
           Y? |  |  |  |  |  |  |  |  |  |
           ---+--+--+--+--+--+--+--+--+--+
    '''
    q_list = sorted(questions.keys())
    top_len = min(3, len(q_list) // 2)
    side_len = len(q_list) - top_len
    top_list = q_list[:top_len]
    side_list = q_list[top_len:]
    sort_codes(questions, top_list)
    sort_codes(questions, side_list)

    top_indent = 2 * side_len + side_len + 2
    for i, q in enumerate(top_list):
        print >> file, "%*s%s%s" % (top_indent, '', '|' * i, q)

    print >> file, "%*s%s" % \
                     (top_indent, '',
                      ' '.join(gray_code(questions[q] for q in top_list)))

    num_top_choices = reduce(operator.mul,
                             (len(questions[q]) for q in top_list))
    horz_line = '-' * (side_len + 1) + \
                ('+' + '-' * top_len) * num_top_choices + '+'
    print >> file, "%*s%s" % (2 * side_len, '', horz_line)
    bars = ' ' + ('|' + ' ' * top_len) * num_top_choices + '|'
    def body():
        for ans in gray_code(questions[q] for q in side_list):
            yield ans + bars
            yield horz_line
    for z in itertools.izip_longest(*side_list + [body()], fillvalue=' '):
        print >> file, ' '.join(z)

def sort_codes(questions, l):
    changed = True
    while changed:
        changed = False
        for i in range(len(l) - 1):
            if len(questions[l[i]]) % 2 != 0 \
               and (len(questions[l[i + 1]]) % 2 == 0 
                    or len(questions[l[i]]) < len(questions[l[i + 1]])):
                l[i], l[i + 1] = l[i + 1], l[i]
                changed = True

def gray_code(digits):
    r'''Generates a gray code for digits.

    Digits is a seq of digit sequences.  All even length digit sequences must
    appear first, followed by all odd length digit sequences in descending len
    order.

        >>> tuple(gray_code(('01',)))
        ('0', '1')
        >>> tuple(gray_code(('01', '01')))
        ('00', '01', '11', '10')
        >>> tuple(gray_code(('01', '012')))
        ('00', '01', '02', '12', '11', '10')
        >>> tuple(gray_code(('012', '012')))
        ('00', '01', '02', '12', '10', '11', '21', '22', '20')
    '''
    def prepare(prior, digit):
        if prior is None: return digit
        if len(prior) % 2 == 0: return reverse(digit)
        reverses = (len(prior) - len(digit)) // 2
        if reverses:
            return itertools.chain(repeat(reverses, reverse(digit)),
                                   cycle(digit))
        else:
            return cycle(digit)
    return product(*((len(digit), prepare(prior, digit))
                     for prior, digit in pairs(digits)))[1]

def pairs(seq):
    r'''Generates pairs from seq.

        >>> tuple(pairs((0, 1, 2)))
        ((None, 0), (0, 1), (1, 2))
    '''
    prior = None
    for x in seq:
        yield prior, x
        prior = x

def product(*seqs):
    r'''Generates the cross product of all of the seqs.

    Each seq in seqs is (len, iterator).

    Returns len, iterator

        >>> l, it = product()
        >>> l, tuple(it)
        (0, ())
        >>> l, it = product((3, '123'))
        >>> l, tuple(it)
        (3, ('1', '2', '3'))
        >>> l, it = product((3, '123'), (2, '45'), (2, '67'))
        >>> l
        12
        >>> tuple(it)
        ('146', '147', '156', '157', '246', '247', '256', '257', '346', '347', '356', '357')
    '''
    if len(seqs) == 0: return 0, ()
    if len(seqs) == 1: return seqs[0]
    len_rest, seq_rest = product(*seqs[1:])
    return seqs[0][0] * len_rest, product1(seqs[0][1], len_rest, seq_rest)

def product1(seq1, seq2_len, seq2):
    r'''Generates the cross product of seq1 and seq2.

    Varies seq2 the fastest.

        >>> tuple(product1('123', 3, '456'))
        ('14', '15', '16', '24', '25', '26', '34', '35', '36')
    '''
    seq2 = iter(itertools.cycle(seq2))
    for i in seq1:
        for j in itertools.islice(seq2, 0, seq2_len):
            yield i + j

def reverse(seq):
    r'''Generates seq forward, then reversed.

        >>> tuple(reverse('012'))
        ('0', '1', '2', '2', '1', '0')
    '''
    t = tuple(seq)
    return itertools.chain(t, t[::-1])

def cycle(seq):
    r'''Cycle through seq starting at each starting position.

    The starting positions start at 0 and rotate backwards through the seq.

        >>> tuple(cycle('012'))
        ('0', '1', '2', '2', '0', '1', '1', '2', '0')
        >>> tuple(cycle('01234'))
        ('0', '1', '2', '3', '4', '4', '0', '1', '2', '3', '3', '4', '0', '1', '2', '2', '3', '4', '0', '1', '1', '2', '3', '4', '0')
    '''
    t = tuple(seq)
    for start in range(len(t), 0, -1):
        for j in range(start, start + len(t)):
            yield t[j % len(t)]

def repeat(n, seq):
    r'''Generates seq n times.

        >>> tuple(repeat(3, '123'))
        ('1', '2', '3', '1', '2', '3', '1', '2', '3')
    '''
    t = tuple(seq)
    for i in range(n):
        for x in t: yield x

def usage():
    sys.stderr.write("usage: make_kmap.py [filename] question1=answers1...\n")
    sys.exit(2)

if __name__ == "__main__":
    if len(sys.argv) < 3: usage()
    if '=' not in sys.argv[1]:
        filename = sys.argv[1]
        qa = sys.argv[2:]
    else:
        filename = None
        qa = sys.argv[1:]
    if len(qa) < 2: usage()
    qa_dict = dict(arg.split('=') for arg in qa)
    if filename:
        with open(filename, 'wt') as f:
            kmap(f, **qa_dict)
    else:
        kmap(**qa_dict)

